#include <vector>
#include <stack>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution
{
public:
    vector<int> nextGreaterElements(vector<int> &nums)
    {
        const int len = nums.size(); // array length
        vector<int> ans(len, -1);       // init ans
        stack<int> stack;               // position records
        for (int i = 0; i < len * 2 - 1; i++)
        {
            const int idx = i % len; // array pos
            while (!stack.empty() && nums[stack.top()] < nums[idx])
            {
                ans[stack.top()] = nums[idx];
                stack.pop();
            }
            stack.push(idx);
        }
        return ans;
    }
};

// 数组转字符串
string arrayToString(const vector<int> &ary)
{
    if (ary.size() == 0)
        return "[]";
    // 结果字符串
    string result;
    for (size_t i = 0, len = ary.size(); i < len; i++)
    {
        // 用数组‘,’形式分隔元素
        result += to_string(ary[i]) + ",";
    }
    // 返回字符串时，添加“[]”，并且移除最后一个','
    return "[" + result.substr(0, result.length() - 1) + "]";
}

int main()
{
    vector<int> arr = {1, 2, 1};
    cout << "want: [2, -1, 2], ans = " << arrayToString(Solution().nextGreaterElements(arr)) << endl;

    vector<int> arr1 = {6, 2, 6, 5, 1, 2};
    cout << "want: [-1, 6, -1, 6, 2, 6], ans = " << arrayToString(Solution().nextGreaterElements(arr1)) << endl;

    vector<int> arr2 = { };
    cout << "want: [], ans = " << arrayToString(Solution().nextGreaterElements(arr2)) << endl;

    return 0;
}